package main

import "fmt"

// 定义链表节点
type ListNode struct {
	Val  int
	Next *ListNode
}

// 插入排序函数
func insertionSortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	// 创建哑节点
	dummy := &ListNode{Next: head}
	// 指向当前待插入的节点
	curr := head
	// 指向已排序部分的尾节点
	prevSorted := head

	for curr != nil && curr.Next != nil {
		// 如果当前节点的值小于等于已排序部分的最后一个节点的值
		if curr.Next.Val < prevSorted.Val {
			// 将当前节点从原位置删除
			tmp := curr.Next
			curr.Next = curr.Next.Next

			// 从头开始遍历已排序部分，找到合适的位置插入
			prev, insertPos := dummy, dummy.Next
			for insertPos.Val <= tmp.Val {
				prev = insertPos
				insertPos = insertPos.Next
			}

			// 插入节点
			prev.Next = tmp
			tmp.Next = insertPos
		} else {
			// 否则，将当前节点移到已排序部分的尾部
			prevSorted = curr.Next
			curr = curr.Next
		}
	}

	return dummy.Next
}

// 打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d", head.Val)
		if head.Next != nil {
			fmt.Printf(" -> ")
		}
		head = head.Next
	}
	fmt.Println("")
}

func main() {
	// 创建一个链表
	head := &ListNode{Val: 4}
	head.Next = &ListNode{Val: 2}
	head.Next.Next = &ListNode{Val: 1}
	head.Next.Next.Next = &ListNode{Val: 3}

	// 打印原始链表
	fmt.Println("原始链表:")
	printList(head)

	// 排序链表
	head = insertionSortList(head)

	// 打印排序后的链表
	fmt.Println("排序后的链表:")
	printList(head)
}
